\documentclass[10pt, a4paper,english,spanish]{article}
\usepackage{listings}
\usepackage{babel}
\usepackage{url}
\usepackage[lined,ruled,linesnumbered,commentsnumbered,algosection,nofillcomment]{algorithm2e}
\usepackage[usenames, dvipsnames]{xcolor}
\parindent = 0 pt
\parskip = 11 pt
\usepackage[width=15.5cm, left=3cm, top=2.5cm, height= 24.5cm]{geometry}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{multicol}

\setlength{\parindent}{1cm}


\begin{document}

\begin{titlepage}

\begin{flushright}
\textbf{\huge{Universidad de Buenos Aires}}\\
\vspace*{10pt}
\textbf{\LARGE{Facultad de Ciencias Exactas y Naturales}}\\
\vspace*{10pt}
\textbf{\Large{Departamento de Computaci\'on}}\\
\vspace*{10pt}
\textbf{\Large{Algoritmos y Estructuras de Datos III}}\\
\textbf{\large{Segundo Cuatrimestre de 2013}}\\
\end{flushright}

\vspace*{5cm}

\begin{center}
\Huge{\textbf{Trabajo Pr\'actico nº 3 \\ \textit{}}}
\end{center}

\vspace*{7cm}

\Large{
\begin{flushright}
Furman, Damián - 936/11 - damian.a.furman@gmail.com\\
Marottoli, Daniela - 42/10 - dani.marottoli@gmail.com\\
Kovacs, Ignacio - 627/10 - ignacio.k91@gmail.com\\
Puerta, Ezequiel - 812/09 - eze19.2009@gmail.com\\
\end{flushright}
}

\
\end{titlepage}

\tableofcontents
\newpage

%~ --------------------------------------------------------------------------------

\section{Introducción}

Sea $G = (V,E)$ un grafo simple. Definimos una \textit{clique} como un subconjunto de $V$ que induce un subgrafo completo de $G$. Definimos también la \textit{frontera} de una clique $K$ como el conjunto de aristas de $G$ que tienen un extremo en $K$ y otro en $V \backslash K$.

El problema sobre el cual se va a basar el presente trabajo práctico consiste en hallar la \textit{clique de máxima frontera} (CMF) de un grafo $G$, es decir, hallar una clique de $G$ cuya frontera tenga cardinalidad máxima. Para esto se desarrollarán distintos tipos de heurísticas, se analizarán, y se compararán en complejidad con un algoritmo exacto que devolverá la solución del problema.

\centerline{\includegraphics[width=1\textwidth]{./intro_ejemplo.png}}

%~ --------------------------------------------------------------------------------

\section{Descripción de Situaciones Reales}
Para encontrar una situación de la vida real que pueda modelarse utilizando CMF, primero analizaremos coloquialmente qué es lo que estamos buscando. 

Llamemos ``relación'' a las aristas (dos nodos $v,u$ están relacionados $\Leftrightarrow (v,u) \in E$ ó $(u,v) \in E$). Al encontrar una clique, conseguimos un conjunto de nodos en el que todos están relacionados entre sí. Asimismo, al calcular la frontera máxima de una clique, estamos buscando el conjunto de nodos relacionados entre sí que tenga la mayor cantidad de relaciones con el resto de los nodos. 

Ahora busquemos una aplicación real. Tomando las redes sociales como ejemplo, llamaremos \textit{personas} a los nodos, y \textit{amistad} a las aristas. Un adolescente quiere agregar como amigos en Facebook, a un grupo de personas que cumplan con las siguientes condiciones: que todos sean amigos entre sí, y que tengan la mayor cantidad de amistades (sin incluir a los que conforman el grupo), con el objetivo de sociabilizar con los ``más populares''. Vale aclarar, que los amigos de las personas del grupo pueden repetirse, pero es un detalle que a este adolescente no le interesa porque no quiere ponerse a identificar amigos en común.

Este problema puede modelarse mediante CMF, ya que la clique sería el grupo de personas que son amigas entre sí, y las amistades son las aristas que salen desde este grupo hacia el resto de los nodos.

\newpage

%~ --------------------------------------------------------------------------------

\section{Algoritmo Exacto}
\subsection{Descripción}

El algoritmo implementado es un algoritmo de backtracking que busca todas las posibles cliques y sus fronteras y se queda con aquella que tenga la frontera máxima. La forma que tiene el algoritmo de recorrer el grafo es tomar un conjunto $P$ de nodos (en su primera llamada arranca con todos los nodos del grafo) y agrega uno cualquiera a la clique. Luego calcula la frontera de la clique y si es mayor que la de la última que se había guardado, la reemplaza por esta nueva. Luego actualiza $P$ dejando sólo los nodos que sean adyacentes a todos los nodos que están en la clique actual. Si $P$ queda vacía luego de esta operación, termina y vuelve. Si no, se llama recursivamente y sigue buscando cliques nuevas que puedan armarse a partir de la que ya tenía armada el algoritmo.

El backtracking implementa una poda que consiste en establecer un orden en el recorrido de los nodos. Toma primero el nodo $1$ y se fija todas las cliques que puede armar con ese nodo. Cuando ya probó todas las combinaciones y pasa al nodo $2$, el algoritmo ya no busca armar ninguna clique nueva que incluya al nodo $1$, dado que esa clique ya habría sido encontrada en el paso anterior. Lo mismo ocurre para las llamadas recursivas. Esto garantiza que no intente buscar dos veces una misma clique y funciona, básicamente, porque al tratarse de un conjunto de nodos no importa verdaderamente el orden en el que estos sean elegidos.

Además se ha considerado que la frontera máxima es menor o igual que la cantidad total de aristas. A medida que el tamaño de la clique correspondiente a la solución va creciendo en cantidad de nodos, el número de aristas pertenecientes a la misma aumenta. Por lo tanto estas aristas, que antes eran parte del total y podían llegar a pertenecer a la frontera buscada, ahora nunca podrán pertenecer a la solución ya que fueron usadas para incrementar el tamaño de la clique y están dentro de la misma. De esto se deduce que:

\begin{center}
$fronteraMaxima \leq m - \frac{(n'-1)*n'}{2}$
\end{center}

Donde $m$ es la cantidad total de aristas en el grafo de la entrada, y $n'$ es la cantidad de nodos pertenecientes a la clique solución.

A partir de este razonamiento se agregó una nueva poda para el algoritmo que consiste en verificar en cada iteración que si encontré la frontera máxima, se debe dejar de iterar, dado que nunca se va a poder mejorar el resultado obtenido.

\subsection{Análisis de Complejidad}

Podemos observar que sin tener en cuenta la llamada recursiva, la complejidad del algoritmo es del orden de $O(n + 2 * log(n)) = O(n)$. Para calcular la complejidad exacta del algoritmo, sin embargo, debemos tener en cuenta la cantidad de veces que el algoritmo se llama a sí mismo. 

Para esto, vamos a tener en cuenta el peor caso: el de un grafo completo, donde todas las combinaciones de nodos son posibles cliques. En este caso, existirá una llamada recursiva por cada subconjunto existente dentro del conjunto de nodos. Si tenemos $n$ nodos, sabemos que existen $2^n$ subconjuntos posibles (dado que para una clique en particular, para cada nodo existen dos posibilidades: está o no está. 

La combinación de todas las posibilidades para todos los nodos es multiplicar la posibilidad de un nodo por sí misma tantas veces como nodos haya).

Podemos inferir, por lo tanto, que la complejidad de nuestro algoritmo es del orden de:

\begin{center}
$O(n*2^n)$.
\end{center}

A continuación observamos el pseudocódigo de nuestro algoritmo de backtracking:

\newpage

\begin{lstlisting}[language=C, numbers=left,
numbersep=15pt,
numberstyle=\tiny,
numberfirstline = false,
breaklines=true,
] 
void backtracking(cliqueActual, gradosActuales, nodosPosibles, cliqueSolucion, fronteraSolucion) {

	if(nodosPosibles.empty())
		return; // O(1)

	set interseccion; // O(1)
	int fronteraNueva; // O(1)
	uint cantAristas = grafo.cantidadAristas(); // O(1)
	
	for(p en nodosPosibles) {
		cliqueActual.insert(p); // O(log n)
		gradosActuales += grafo.miGrado(p); // O(1)
		fronteraNueva = gradosActuales - ( cliqueActual.size() * 
			(cliqueActual.size()-1) ); // O(1)
		
		if(fronteraSolucion < fronteraNueva) {
			fronteraSolucion = fronteraNueva; // O(1)
			cliqueSolucion = cliqueActual; // O(1)
		}
		
		if(fronteraSolucion == 
			cantAristas - cliqueActual.size()) { // O(1)
			return; // O(1)
		}
		
		interseccion = 
			grafo.adyacentes(p, nodosPosibles); // O(n)
		
		backtracking(cliqueActual, gradosActuales, interseccion, cliqueSolucion, fronteraSolucion);
		
		cliqueActual.erase(p); // O(log n)
		gradosActuales -= grafo.miGrado(p); // O(1)
	}
}
\end{lstlisting}

\subsection{Casos de prueba y gráficos}
%- Gráfico de complejidad

\subsection{Código Fuente}

\begin{verbatim}
void CliqueMaximaFronteraExacto::backtracking(set<uint> &R, uint &gradosActuales, 
    set<uint> P, set<uint> &res, uint &cantRes) {
    
    if(P.empty())
        return;

    set<uint> interseccion;
    int fronteraNueva;
    uint cantAristas = grafo.cantidadAristas();
    
    for(set<uint>::iterator it = P.begin(); it != P.end(); it++) {
        R.insert(*it);		
        gradosActuales += grafo.miGrado(*it);
        fronteraNueva = gradosActuales - R.size() * (R.size()-1);
        
        if(cantRes < fronteraNueva) {
            cantRes = fronteraNueva;
            res = R;		
        }
        
        if(cantRes == cantAristas - R.size()) {
            return;
        }
        
        interseccion = grafo.adyacentes(*it, P);
        backtracking(R, gradosActuales, interseccion, res, cantRes);
        
        R.erase(*it);
        gradosActuales -= grafo.miGrado(*it);
    }
}
\end{verbatim}

\newpage

\section{Heurística Constructiva Golosa}

\subsection{Descripción}
El método adoptado por la heurística golosa constructiva se basa en tomar el nodo de mayor grado (que es la clique de tamaño $1$ de máxima frontera entre todas las cliques de tamaño $1$), agregarlo a la clique y a partir de ese nodo ir construyendo una mejor solución. La forma de construir esa mejor solución es ir agregando iterativamente los nodos adyacentes a todos los que ya están en la clique de tal manera que se forme una clique nueva. En caso de que haya más de un nodo que pueda agregar, siempre toma el de mayor grado. Si esa clique tiene mayor o igual frontera que la anterior, sigo buscando nuevos nodos para agregar. Si tiene menor frontera, termina y devuelve la clique actual como solución. 

%REVISAR ESTE PÁRRAFO
Nótese que el hecho de tomar siempre el nodo de mayor grado de entre todos los nodos posibles que puedo agregar garantiza que si el nodo que elegí disminuye la frontera de la clique, no existe otro nodo que pueda agregar en vez de ese que haga que la frontera aumente (por lo menos no de manera inmediata). Esto sucede  porque si tengo una clique de k nodos y quiero agregar un nuevo nodo $i$, la frontera de la nueva clique va a aumentar si y sólo si el grado de $i$ es mayor a $k - 1$. Si asumimos que el nodo $i$ es el de mayor grado y no se cumple que $d(i) \geq k - 1$ entonces no existe ningún otro nodo que cumpla esta condición. Si existiera, entonces el nodo $i$ no podría haber sido el de mayor grado.

Ésto nos sirve para demostrar que la golosa alcanza un máximo local. Esto quiere decir, que si definimos que una solución $C_{1}$ es vecina a toda solución $C_{2}$ tal que $C_{2} = C_{1} + algún nodo v_{i}$ con $v_{i} \in V$ no existen soluciones vecinas que tengan mayor frontera que la solución de nuestra heurística golosa. En particular, si existiera una o más soluciones con mayor frontera agregándole un nodo, una de estas soluciones debería ser la de agregar el nodo de mayor grado que forma clique. Pero si este nodo no forma parte de la solución de nuestro algoritmo es porque agregarlo no aumentaba la frontera y por lo tanto, por lo demostrado anteriormente, ninguno de los nodos que forman una clique nueva aumenta la frontera.

Esta demostración nos va a servir más adelante para demostrar por qué no resulta útil combinar el resultado de nuestra heurística golosa con nuestra heurística local o tabú.


\subsection{Análisis de Complejidad}
Observemos el pseudocódigo de nuestra heurística constructiva golosa:

\begin{lstlisting}[language=C, numbers=left,
numbersep=15pt,
numberstyle=\tiny,
numberfirstline = false,
breaklines=true,
]
set resolver() {
	set solucion; // O(1)
	set nodos = grafo.conjuntoNodos(); // O(1)
	uint fronteraActual = 0; // O(1)
	uint fronteraMaxima = 0; // O(1)
	uint gradosActuales = 0; // O(1)
	
	while (true) {
		if (nodos.empty()) // O(1)
			break;
			
		uint nodoMaxGrado = maximo(nodos); // O(n)
		gradosActuales += grafo.miGrado(nodoMaxGrado); // O(1)
		fronteraActual = gradosActuales - 
			solucion.size() * (solucion.size()+1); // O(1)
		
		if (fronteraMaxima < fronteraActual) { // O(1)
			solucion.insert(nodoMaxGrado); // O(1)
			nodos = grafo.adyacentes(nodoMaxGrado, 
				nodos); // O(n)
			fronteraMaxima = fronteraActual; // O(1)
		} else {
			break;
		}
	}
	
	return solucion; // O(1)
}
\end{lstlisting}

Podemos observar que para cada iteración nuestro código hace dos operaciones del orden de $O(n)$ (en peor caso) que consisten en encontrar el nodo de mayor grado de entre los nodos que puedo agregar a mi clique. Notemos que el peor caso consiste en un grafo completo, para el cual al elegir cualquiera de los nodos, los nodos adyacentes siguen siendo todos los nodos del grafo. En este caso, la cantidad de iteraciones que va a realizar (suponiendo que de alguna manera cada nodo que agregue a mi clique amplíe la frontera) será $n$ (una iteración por cada nodo). Y la operación de encontrar el máximo entre los nodos que no agregué a mi clique será $n$ la primera vez, $n - 1$ cuando ya haya agregado un nodo, etc. La complejidad final de nuestra heurística entonces, está dada por la cota $O(\sum_{i=0}^{n} i) = O(\frac{n*(n+1)}{2}) = O(n^2)$.

\subsection{Instancias}
Considerando que la implementación se trata de una heurística, existe la posibilidad de que no se devuelva la solución óptima. Esto se daría en el caso en el que el nodo de mayor grado no formara parte de la clique de máxima frontera, como se ve en el ejemplo a continuación:

\centerline{\includegraphics[width=1\textwidth]{./goloso_contraejemplo.png}}

Otro contraejemplo más inusual, puede darse en el siguiente caso, en el que el nodo de mayor grado sí forma parte de la clique de máxima frontera, pero el siguiente nodo que se elije considerando los grados de mayor a menor, no:

\centerline{\includegraphics[width=1\textwidth]{./grafo_deforme_golosa.png}}

Asímismo puede extenderse el ejemplo anterior a los casos en el que el nodo mal elegido no sea el segundo, sino cualquiera en la lista de adyacencias.

Sin embargo, estos ejemplos no son fáciles de encontrar; lo más común es que el nodo de grado máximo pertenezca a la clique de máxima frontera. Todo esto tratándose de grafos relativamente pequeños, y sin importar que sean conexos o no conexos.

Sin embargo, si tratáramos con grafos de mayor tamaño, el error aumentaría notoriamente, como veremos en los gráficos de la siguiente sección.


\subsection{Casos de prueba y gráficos}
%- Comparación con el exacto - devolver la frontera máxima en ambos casos
%- Gráficos de complejidad


\subsection{Mejora}
%- Ver si agregamos la mejora (que consiste en recorrer todos los nodos en vez de agarrar al boleo el de mayor grado)
% Poner que la mejora solucionaría todos los casos anteriores pero aumentaría la complejida de n cuadrado a n cubo y que aún quedaría un caso sin resoler (el del cuadrado que todos los nodos están en dos cliques y una de esas cliques tiene un nodo de mayor grado)


\section{Heurística de Búsqueda Local}

\subsection{Descripción}

La heurística de búsqueda local consiste en obtener una solución parcial, y recorrer su vecindad de manera que la frontera obtenida sea mayor.
La \textit{solución parcial inicial} es tomada por parámetro por la función, pero en caso de que no se le pase ninguna la heurística toma por defecto la clique de dos nodos cuya frontera sea la mayor de todas las cliques de dos nodos del grafo.
La \textit{vecindad} de soluciones se define de la siguiente manera: una clique $C_{1}$ es vecina a otra clique $C_{2}$ si existe un par de nodos adyacentes que no sea subgrafo de $C_{1}$ tal que al unirla a $C_{1}$ obtenemos $C_{2}$ (observar que $C_{1}$ puede tener uno de sus nodos en común con el par de nodos adyacentes).

Dicho esto, procedemos a desarrollar los pasos a seguir de la heurística:\\
En primer lugar, se obtienen todas las posibles cliques binódicas del grafo. Notar que un nodo en particular puede pertenecer a más de una clique. Luego, se las coloca en una lista y se las ordena descendentemente según el tamaño de su frontera.
Luego chequeamos si existe una solución parcial pasada por parámetro. Si no es así, tomamos el primer elemento de la lista de pares de nodos adyacentes (clique binódica de máxima frontera) y la definimos como solución parcial inicial. A partir de esta solución, buscamos una solución vecina, es decir, recorremos la lista de cliques binódicas hasta encontrar la primera que al unirla forme una clique, y que además aumente la frontera. Una vez que se encuentra, se agrega a la solución de manera de obtener una nueva y mejor solución parcial. Este procedimiento se repite hasta que la frontera de la solución parcial no pueda mejorarse más. Se puede observar que el tamaño de las soluciones puede aumentar tanto de a uno como de a dos nodos. 

\subsection{Análisis de Complejidad}

A continuación observamos el código fuente de nuestra heurística de busqueda local:

\begin{lstlisting}[language=C, numbers=left,
numbersep=15pt,
numberstyle=\tiny,
numberfirstline = false,
breaklines=true,
]


vector<uint> CliqueMaximaFronteraLocal::resolver(vector<int> &clique) {		

list<vector<int> > cliques_binodos;  // $O(1)$


//Arma todas las cliques binódicas

int tam = grafo.cantidadNodos();  // $O(1)$

for(int i = 0; i < tam; i++){ // $O(n)$
	for(int j = i; j < tam; j++){ // $O(n)$
		vector<int> aux;  // $O(1)$
		if(grafo.adyacencia[i][j]){  // $O(1)$
			aux.push_back(i + 1);  // $O(1)$
			aux.push_back(j + 1);  // $O(1)$
			aux.push_back(grafo.miGrado(i + 1) + grafo.miGrado(j + 1) - 2);  // $O(1)$
			cliques_binodos.push_back(aux);  // $O(1)$
		}
	}
}

cliques_binodos.sort(tercer_orden);  // $O(m log m)$


//Aca empieza a recorrer las vecindades

vector<int> aux_binodo;   // $O(1)$

bool tienen_iguales;  // $O(1)$

bool termine = false;  // $O(1)$

int repetido;  // $O(1)$

vector<int> CMFLocal;  // $O(1)$

if(clique.empty())  // $O(1)$
{
	CMFLocal = cliques_binodos.front();  // $O(1)$
	cliques_binodos.pop_front();  // $O(1)$
}
else
{
	CMFLocal = clique;  // $O(1)$
}

list<vector<int> > cliques_binodos_aux = cliques_binodos;  // $O(m)$

bool encontre_clique;  // $O(1)$

while(!termine){

encontre_clique = false;  // $O(1)$

	while(!(encontre_clique) && !(termine)){

	aux_binodo = cliques_binodos_aux.front();  // $O(1)$
	cliques_binodos_aux.pop_front();  // $O(1)$
	tienen_iguales = false;  // $O(1)$

		if(esCliqueMayorFrontera(CMFLocal, aux_binodo, tienen_iguales, repetido)){  // $O(n)$

			CMFLocal = unir(CMFLocal, aux_binodo, tienen_iguales, repetido);  // $O(1)$
			encontre_clique = true;  // $O(1)$
			cliques_binodos.remove(aux_binodo);  // $O(m)$
		}


	if(cliques_binodos_aux.empty()){ termine = true; }  // $O(1)$

	}

}

vector<uint> resultado;  // $O(1)$

int CMFtam = CMFLocal.size() -1;  // $O(1)$
resultado.push_back(CMFLocal[CMFtam]);  // $O(1)$
resultado.push_back(CMFtam);  // $O(1)$

	for(int k = 0; k < CMFtam; k++){   // $O(n)$

		resultado.push_back(CMFLocal[k]);

	}

return resultado;  // $O(1)$

}

\end{lstlisting}

Para calcular la complejidad del algoritmo, podemos dividirlo en dos etapas. La primera consiste en tomar todos los pares de nodos adyacentes entre sí y ordenarlos según el tamaño de su frontera. La segunda etapa consiste en ir agregándole esos nodos a mi solución parcial hasta llegar a un máximo local. Vamos a asumir que la solución parcial con la que empezamos es trivial para que el calculo de complejidad se realice sobre la base de un análisis de peor caso.

Para la parte 1, el algoritmo recorre la matriz de adyacencia con dos fors anidados. La complejidad de esa operación es del orden de $O(n^2)$. Luego ordena todos los pares de nodos adyacentes. La cantidad de pares de nodos adyacentes es igual a la cantidad de aristas, es decir, m. La complejidad del ordenamiento por lo tanto es del orden de $O(m log m)$. En total, para la primera parte de nuestro algoritmo, por lo tanto, la complejidad es de $O(n^2 + m log m)$.

Entre la primera y la segunda parte, el algoritmo realiza una operación auxiliar que consiste en copiar la lista de pares de nodos adyacentes, necesaria para preservar esta lista en las modificaciones sucesivas que el algoritmo realizará sobre ella. Esta operación auxiliar es del orden de $O(m)$ dado que realiza una copia para cada una de las adyacencias.

En lo que denominamos la segunda parte de nuestro algoritmo, tomamos nuestra solución parcial y vemos si podemos agregarle alguna de las adyacencias de nuestra lista ordenada previamente. La operación de comprobar para un par de nodos adyacentes si se los podemos agregar a nuestra solución parcial y mejorarla consiste en comparar los dos nodos del par con cada uno de los nodos de nuestra solución parcial. Como la cantidad de nodos del par adyacente está acotada (son dos), la complejidad depende exclusivamente de la cantidad de nodos que pueda tener nuestra solución parcial. En particular, sabemos que nuestra solución parcial nunca puede llegar a tener n nodos (porque entonces su frontera sería 0), sin embargo, existe un peor caso en que la clique de máxima frontera pueda tener $n/2$ nodos (para un grafo completo, por ejemplo, este valor maximiza la frontera de la clique subgrafo del grafo completo). Por lo tanto, asumiendo este peor caso, vamos a tomar la operación de comprobar si un par de nodos mejora nuestra solución parcial en el orden de $O(n)$. Esta operación, además, vamos a realizarla m veces (una para cada par de nodos adyacentes). Por lo que mejorar nuestra solución parcial es del orden de $O(n*m)$. Pero para cada par que encontramos que mejora efectivamente nuestra solución, debemos luego eliminar el par de nodos adyacentes de la lista de adyacencias, lo que tiene una complejidad de $O(m)$. Esto lleva la complejidad de mejorar una vez nuestra solución parcial a $O(n*m + m) = O((n+1)*m) = O(n*m)$.

Queda ver ahora cuantas veces podemos llegar a mejorar nuestra solución parcial. Observamos que al agregarle un par de nodos adyacentes, tenemos dos posibilidades: que uno de esos nodos ya pertenezca a nuestra solución o no (si el par adyacente es subgrafo de nuestra solución parcial la función \texttt{esCliqueMayorFrontera} lo descarta). Es decir que asumiendo el peor caso posible, cada vez que mejoramos nuestra solución esta puede llegar a mejorar en tan solo un nodo. Ya comentamos unas líneas más arriba que nuestra solución puede crecer hasta $n/2$ nodos. Como asumimos el peor caso en el que nuestra solución inicial es trivial (un nodo), la cantidad de operaciones de mejoramiento de nuestra solución parcial está en el orden de $O(n)$. La complejidad total de lo que llamamos la segunda parte de nuestro algoritmo, por lo tanto, está en el orden de $O(n^2*m)$.

Finalmente, la complejidad total de nuestro algoritmo está en el orden de $O(n^2*m + n^2 + m log m) = O((m + 1) * n^2 + m log m) = O(m * n^2 + m log m) = O(m * (n^2 + log m))$

\subsection{Instancias Defectuosas}

En primer lugar, hay que tener en cuenta que las instancias mejores o peores dependen de la solución inicial con la que nuestro algoritmo comience a ejecutarse. En particular, observamos que la relación de vecindad es una función que va de un grafo con $n$ nodos a un grafo con $n + 1$ o $n + 2$ nodos. Por lo tanto, si una clique $C_{1}$ es vecina de otra clique $C_{2}$, $C_{2}$ no puede ser vecina de $C_{1}$. En particular esta consideración sirve para observar que si la solución parcial pasada por parámetro ya es un máximo local entonces nuestra heurística de busqueda local va a ser incapaz de mejorarla.

Para el caso particular de la solución parcial tomada por defecto (la clique de máxima frontera de dos nodos) podemos encontrar una instancia de grafos en la cual la falla de la heurística es muy evidente, y es aquella en la que la clique de máxima frontera consta de exactamente un nodo. 

\centerline{\includegraphics[width=0.7\textwidth]{./clique_1_nodo.png}}

En este caso la solución inicial constaría de una clique de dos nodos, por lo que la verdadera solución nunca sería alcanzada.

Además, como mostramos en la heurística golosa, hay otro contraejemplo que se produce cuando alguno de los nodos de la solución inicial (o de cualquier otra solución parcial vecina) no pertenece a la solución real. En el siguiente dibujo vemos cómo actúa la heurística y cuál es la solución real:

\centerline{\includegraphics[width=1\textwidth]{./deforme_local.png}}

Sin embargo, disminuye en alguna medida las fallas producidas por la heurística golosa que se dan al elegir al nodo incorrecto en primera instancia (es decir, cuando el de mayor grado no pertenece a la clique de máxima frontera), ya que el margen de error se reduce al agregarle más condiciones (se elige la clique de tamaño dos de mayor frontera, en vez de tamaño uno).  Vemos en el contraejemplo presentado anteriormente cómo se elige la solución correcta gracias a esta mejora:

\centerline{\includegraphics[width=1\textwidth]{./mejora_la_golosa.png}}


\subsubsection{Relación con la heurística golosa}

En la sección correspondiente a la heurística golosa hemos determinado un criterio de vecindad que consiste en que dos soluciones son vecinas si puedo formar una agregándole un nodo a la otra. Según estre criterio, demostramos que la heurística golosa alcanza un máximo local. Según el criterio de vecindad adoptado para definir nuestra heurística de búsqueda local también podemos definir a la solución aportada por la heurística golosa como un máximo local. Esto quiere decir que no existe una solución vecina (en los terminos de la busqueda local, es decir, agregándole un par de nodos adyacentes) a la clique que devuelve como resultado la heurística golosa tal que esa solución mejore su frontera. Para demostrar esto vamos a tomar dos casos:

a) el par de nodos adyacentes que queremos agregar tiene un nodo en común con la solución de nuestra heurística golosa. En este caso, se llega a la solución nueva agregando un nodo. Entonces, esta nueva solución es una solución vecina en los terminos de la relación de vecindad que inventamos cuando analizamos el caso de la heurística golosa. Pero cuando analizamos ese caso ya demostramos que la solución que proveía nuestro algoritmo era un máximo local. Por ende, es un máximo local también utilizando el criterio de vecindad de la heurística de busqueda local.

b) el par de nodos adyacentes que queremos agregar no tiene nodos en común con la solución de nuestra heurística golosa. Supongamos que existe un par de nodos adyacentes tal que podamos agregárselos a la solución de nuestra heurística golosa y formar una clique con mayor frontera. Como sabemos que la solución de la heurística golosa es un máximo local (según el criterio definido en la sección correspondiente) sabemos que no existe un nodo que podamos agregarle tal que se forme una nueva clique de mayor frontera. Sin embargo, existe un par de nodos adyacentes que no tienen nodos en común con la solución de nuestra heurística golosa que sí podemos agregarlos formando una clique de mayor frontera. Es decir que si agregamos esos nodos en orden, el primero que agregamos debería disminuir la frontera y el segundo aumentarla. Llamemos $v_{1}$ al nodo que al agregarlo hace disminuir la frontera de nuestra solución y $v_{2}$ al que hace que nuestra frontera aumente. Sea $n$ la cantidad de nodos de la solución de la heurística golosa, si agregamos primero $v_{1}$ a esa solución, para que la frontera aumente al agregarle luego $v_{2}$ el grado de $v_{2}$ debe cumplir $d(v_{2}) - (n + 1) \geq 0$. Ahora bien, si al agregar $v_{2}$ a la solución de la heurística golosa más $v_{1}$ se forma una clique, esto significa que $v_{2}$ es adyacente a todos los nodos de la solución de la golosa y a $v_{1}$, pero en particular a todos los nodos de la solución de la heurística golosa. Por lo tanto, agregarle $v_{2}$ directamente a la solución de la heurística golosa también debería formar una clique. Y como sabemos que $d(v_{2}) - (n + 1) \geq 0$, en particular también se cumple que $d(v_{2}) - n \geq 0$. Por lo tanto, esto significa que podemos agregarle $v_{2}$ a la solución aportada por la golosa y se forma una clique con mayor frontera. Pero esto es absurdo porque la solución de la heurística golosa es un máximo local.

Esta demostración sirve para observar que la heurística planteada de búsqueda local no mejora ninguna de las soluciones que pueda aportar la heurística golosa y por lo tanto no tiene sentido utilizarlas en combinación.



\subsection{Casos de prueba y gráficos}
%- Gráficos de complejidad
%- Comparación con el exacto - devolver la frontera máxima en ambos casos
%- Comparación con el goloso - devolver la frontera máxima en ambos casos - también comparación de tiempos


\section{Heurística de Búsqueda Tabú}

\subsection{Descripción}

La metaheurística de busqueda tabú está basada en la heurística de busqueda local, con la diferencia que al encontrar un máximo local la heurística de busqueda tabú agrega ese máximo a una lista de soluciones tabú (para no volver a recorrerla) y luego vuelve a comenzar a partir de la ultima solución parcial encontrada (es decir, vuelve un paso para atrás, lo que significa sacarle el o los últimos nodos agregados). Al realizar esto, la busqueda tabú aumenta un contador que se inicializa inicialmente en 0 y que al llegar a 10 (es decir al encontrar 10 máximos locales distintos) se detiene. Finalmente, compara todas las soluciones parciales encontradas para determinar cual es la mejor y la devuelve. La heurística de busqueda tabú, por lo tanto, mejora sustancialmente el rendimiento de la heurística de busqueda local dado que utiliza el mismo método para encontrar un máximo local pero en vez de devolver el primero que encuentra, sigue buscando hasta encontrar diez y luedo compara entre estos 10 para encontrar la mejor solución.


\subsection{Análisis de Complejidad}

Nuestra heurística de búsqueda tabú está basada en la heurística local explicada en la sección anterior de nuestro trabajo.

Las modificaciones introducidas implican que al encontrar una solución de máximo local el algoritmo retroceda a una solución parcial anterior y vuelva a ejecutarse desde ese nivel. Cada vez que hace esto, aumenta un contador. El algoritmo se detiene cuando ese contador alcanza el 10.

Las operaciones necesarias para retroceder a una solución parcial anterior implican guardar la solución parcial cada vez que vamos a aplicarle una mejora. Como determinamos que una solución parcial puede tener a lo sumo $n/2$ nodos, guardar ese valor es del orden de $O(n)$. Como ya argumentamos en la sección correspondiente a la heurísitca de búsqueda tabú, una solución puede mejorar a lo sumo $n/2$ veces. Por lo tanto, estas operaciones adicionales a la busqueda tabú están en el orden de $O(n^2)$. Incluso esta complejidad puede acotarse mucho más, dado que podemos argumentar que las soluciones parciales que guardamos son proporcionales a la cantidad de mejoras que ya le aplicamos a nuestra solución parcial. Pero aún así, podemos observar que la complejidad de la heurística busqueda tabú es del orden de $O(10 * (n^2 + O(heurística de busqueda local))) = O(10 * (n^2 + (n^2 + log m) * m)) = O(n^2 + (n^2 + log m) * m) = O((n^2 + log m) * m) = O(heurística de busqueda local)$


\subsection{Instancias Defectuosas}

\subsection{Casos de prueba y gráficos}
%- Gráficos de complejidad
%- Comparación con el exacto - devolver la frontera máxima en ambos casos
%- Comparación con el goloso - devolver la frontera máxima en ambos casos - también comparación de tiempos
%- Comparación con la búsqueda local - devolver la frontera máxima en ambos casos - también comparación de tiempos

\subsection{El Tabú por parámetro}

Una posible modificación de nuestra heurística consiste en pasarle por parámetro al algoritmo cuantos máximos locales queremos que encuentre antes de detenerse. Esto permite que quien va a utilizar el algoritmo tenga la posibilidad de decidir entre precisión y complejidad temporal. En este caso, si llamamos al parámetro de cuantos tabues queremos que marque (cuantos máximos locales encuentra), $k$, la complejidad temporal del algoritmo pertenecería al orden de $O(k * m * (n^2 + log m))$.

\section{Conclusiones generales}

- Tabú le rompe el orto a la busqueda local
- La golosa gana en cuanto a complejidad temporal
- La golosa mejorada gana más
- ninguna de las que hicimos se pueden combinar :(

\end{document}

